#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<string.h>
using namespace std;
const int MAXN = 1010;
const int MAXM = 110;
int w[MAXN];
int v[MAXM];
int dp[MAXM][MAXN];
int main()
{
	int n, m;
	while (cin >> m >> n)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> w[j] >> v[j];
			for (int i = 1; i <= m; i++)
			{
				if(i>=w[j])
					dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - w[j]] + v[j]);
				else 
					dp[j][i] = dp[j - 1][i];

			}
		}
		cout << dp[n][m] << endl;
		vector<int>path;
		while (n)
		{
			if (dp[n][m] != dp[n - 1][m])
			{
				path.push_back(n);
				m -= w[n];
			}
			n--;
		}
		for (int i = path.size() - 1; i >= 0; i--)
		{
			if(i==0)
				cout << path[i];
			else
				cout << path[i] << ' ';
		}
		if(path.size()>0)
			cout << endl;
		memset(dp, 0, sizeof(dp));
	}
	return 0;
	
}